#include <climits>
#include <cstdio>
#include <vector>
using namespace std;

struct edge {
    int next;
    int cost;
    int thin_path;
};
vector<edge> edge_data[501];

bool mark[501];
long long distance_record[501];
int pre_record[501];

long long get_path_length(int now_node, int index);

int main(int argc, char const* argv[])
{

    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        mark[i] = false;
        distance_record[i] = -1;
        pre_record[i] = -1;
        edge_data[i].clear();
    }

    for (int i = 0; i < m; i++) {
        int thin_path, a, b, cost;
        scanf("%d%d%d%d", &thin_path, &a, &b, &cost);
        edge temp;
        temp.thin_path = thin_path;
        temp.cost = cost;
        temp.next = b;
        edge_data[a].push_back(temp);
        temp.next = a;
        edge_data[b].push_back(temp);
    }

    int start_node = 1;
    mark[start_node] = true;
    distance_record[start_node] = 0;
    pre_record[start_node] = 0;
    int now_node = start_node;

    for (int i = 0; i < m - 1; i++) {
        for (int j = 0; j < edge_data[now_node].size(); j++) {
            int next_node = edge_data[now_node][j].next;
            int cost = edge_data[now_node][j].cost;
            if (mark[next_node])
                continue;
            long long total_cost;
            if (!edge_data[now_node][j].thin_path)
                total_cost = distance_record[now_node] + cost;
            else{
                //pre_record[next_node] = now_node;
                total_cost = get_path_length(now_node, j);
            }
            if (distance_record[next_node] == -1 || total_cost < distance_record[next_node]) {
                distance_record[next_node] = total_cost;
                pre_record[next_node] = now_node;
            }
        }
        int min = INT_MAX;
        for (int j = 1; j <= n; j++) {
            if (mark[j])
                continue;
            if (distance_record[j] == -1)
                continue;
            if (distance_record[j] < min) {
                min = distance_record[j];
                now_node = j;
            }
        }
        mark[now_node] = true;
    }
    printf("%lld\n", distance_record[n]);
    return 0;
}

long long get_path_length(int now_node, int index)
{
    long long total_thin_path = edge_data[now_node][index].cost;
    long long total_cost = distance_record[now_node] + total_thin_path * total_thin_path;
    int pre_node = pre_record[now_node];
    int now_node_index;
    while (pre_node != 0) {
        for (int i = 0; i < edge_data[pre_node].size(); i++) {
            if (edge_data[pre_node][i].next == now_node) {
                now_node_index = i;
                break;
            }
        }

        if (edge_data[pre_node][now_node_index].thin_path) {
            total_thin_path += edge_data[pre_node][now_node_index].cost;
            now_node = pre_node;
            pre_node = pre_record[pre_node];
            total_cost = distance_record[now_node] + total_thin_path * total_thin_path;
        } else {
            total_cost = distance_record[now_node] + total_thin_path * total_thin_path;
            break;
        }
    }

    return total_cost;
}